#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <string.h>
using namespace std;
/*
问题：凑出金额为amount的有多少的组合方式,每种数字的金币都无限个，所以，
金币的数值和个数都不算变量
解法：回溯
*/
vector<vector<int> > res;
map<string, int> memo; //int:target, string
void change(int amount, vector<int>& coins, vector<int>& track) 
{
    /*
    判断触底条件
    回溯二叉树叶子节点为0即结束，剪枝：将结点小于0剪枝
    最终计算叶子节点为0的分支的个数
    */

    //带记忆的回溯，排除重复解

    if (amount < 0) return;
    if (0 == amount)
    {
        vector<int> temp(track);
        res.push_back(track);
        return;
    }
    //消除重复问题
    vector<int> temp(coins);
    for (unsigned int j = 1; j <= coins.size() - 1; j++){
        for (unsigned int k = 0; k <= coins.size() - 2; k++){
            if (temp[k] > temp[k+1]){
                int t = temp[k+1];
                temp[k+1] = temp[k];
                temp[k] = t;
            }
        }
    }
    string key = ""; 
    for (unsigned int j = 0; j < temp.size(); j++)
    {
        key += to_string(temp[j]);
    }
    map<string, int>::iterator it;
    for(it = memo.begin(); it != memo.end(); it++)
    {
        //属于重复计算问题
        if (it->first == key)
            return;
    }

    for (unsigned int i = 0; i < coins.size(); i++)
    {
        track.push_back(coins[i]);
        change(amount - coins[i], coins, track);
        track.pop_back(); 
    }
    memo.insert(pair<string, int>(key, 0));

}

int main()
{
    int amount = 5;
    vector<int> coins = {1, 2, 5}; 
    vector<int> track;
    change(amount, coins, track);
    cout << res.size() << endl;
    return 0;
}